% Created 2019-07-17 三 14:10
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\input{preamble.tex}
\author{wu}
\date{\today}
\title{Rough Sets: Theoretical aspects of reasoning about data}
\hypersetup{
 pdfauthor={wu},
 pdftitle={Rough Sets: Theoretical aspects of reasoning about data},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 26.2 (Org mode 9.2.4)}, 
 pdflang={English}}
\begin{document}

\maketitle
\tableofcontents \clearpage\section{Knowledge}
\label{sec:org90be6f7}
\subsection{Knowledge base}
\label{sec:org4d3ee0e}
Given a finite set \(U\neq \emptyset\) (the universe). Any subset \(X\subset U\)
of the universe is called a \textbf{concept} or a \textbf{category} in \(U\). And any family of
concepts in \(U\) will be referred to as \textbf{abstract knowledge} about \(U\).

\textbf{partition} or \textbf{classification} of a certain universe \(U\) is a family 
\(C=\lb X_1,X_2,\dots,X_n\rb\) s.t. \(X_i\subset U,X_i\neq\emptyset,X_i\cap
   X_j=\emptyset\) and \(\bigcup X_i=U\)

A family of classifications is called a \textbf{knowledge base} over \(U\)


\(R\) an equivalence relation over \(U\), \(U/R\) family of all equivalence classes
of \(R\), referred to be \textbf{categories} or \textbf{concepts} of \(R\), and \([x]_R\) denotes a
category in \(R\) containing an element \(x\in U\)

By a \textbf{knowledge base} we can understand a relational system \(K=(U,\bR)\), \(\bR\)
is a family of equivalence relations over \(U\)

If \(\bP\subset \bR\) and \(\bP\neq\emptyset\), then \(\bigcap\bP\) is also an
equivalence relation, and will be denoted by \(IND(\bP)\), called an
\textbf{indiscernibility relation} over \(\bP\)
\begin{equation*}
[x]_{IND(\bP)}=\bigcap_{R\in\bP}[x]_R
\end{equation*}

\(U/IND(\bP)\) called \(\bP\textbf{-basic}\) \textbf{knowledge about} \(U\) in \(K\). For
simplicity, \(U/\bP=U/IND(\bP)\) and \(\bP\) will be also called
\(\bP\textbf{-basic}\) \textbf{knowledge}
. Equivalence classes of \(IND(\bP)\) are called
\textbf{basic categories} of knowledge \(\bP\). If \(Q\in\bR\), then \(Q\) is a
\(Q\textbf{-elementary}\) \textbf{knowledge} and equivalence classes of \(Q\) are referred
to as \(Q\textbf{-elementary}\) \textbf{concepts} of knowledge \(\bR\)

The family of all \(\bP\text{-basic}\) categories for all
\(\empty\neq\bP\subset\bR\) will be called the \textbf{family of basic categories} in
knowledge base \(K=(U,\bR)\)

Let \(K=(U,\bR)\) be a knowledge base. By \(IND(K)\) we denote the family of all
equivalence relations defined in \(K\) as \(IND(K)=\lb
   IND(\bP):\emptyset\neq\bP\subseteq\bR\rb\).

Thus \(IND(K)\) is the minimal set of equivalence relations.

Every union of \(\bP\text{-basic}\) categories will be \(\bP\textbf{-category}\)

The family of all categories in the knowledge base \(K=(U,\bR)\) will be
referred to as \(K\textbf{-categories}\)
\subsection{Equivalence, generalization and specialization of knowledge}
\label{sec:org48c8b20}
Let \(K=(U,\bP),K'=(U,\bQ)\). \(K\) and \(K'\) are \textbf{equivalent} \(K\simeq
   K',(\bP\simeq\bQ)\) if \(IND(\bP)=IND(\bQ)\). Hence \(K\simeq K'\) if both \(K\) and
\(K'\) have the same set of elememtary categories. \emph{This means that knowledge in
knowledge bases \(K\) and \(K'\) enables us to express exactly the same facts about the universe.}

If \(IND(\bP)\subset IND(\bQ)\) then knowledge \(\bP\) is \textbf{finer} than knowledge
\(\bQ\) (\textbf{coarser}). \(\bP\) is \textbf{specialization} of \(\bQ\) and \(\bQ\) is \textbf{generalization}
of \(\bP\)
\section{Imprecise categories, approximations and rough sets}
\label{sec:org433d79a}
\subsection{Rough sets}
\label{sec:org008770b}
Let \(X\subseteq U\). \(X\) is \(R\textbf{-definable}\) or \(R\textbf{-exact}\) if \(X\) is the union of some
\(R\text{-basic}\) categories. otherwise
\(R\textbf{-undefinable},R\textbf{-rough},R\textbf{-inexact}\)  .
\subsection{Approximations of set}
\label{sec:org9d1bdb4}
Given \(K=(U,\bR), R\in IND(K)\)
\begin{align*}
&\underline{R}X=\bigcup\lb Y\in U/R:Y\subseteq X\rb\\
&\overline{R}X=\bigcup\lb Y\in U/R:Y\cap X\neq\emptyset\rb\\
\end{align*}
called the \(R\textbf{-lower}\) and \(R\textbf{-upper}\) \textbf{approximation} of \(X\)

\(BN_R(X)=\overline{R}X-\underline{R}X\) is \(R\textbf{-boundary}\) of \(X\).
\(BN_R(X)\) is the set of elements which cannot be classified either to \(X\) or
to \(-X\) having knowledge \(R\)

\begin{align*}
&POS_R(X)=\underline{R}X,R\text{-positive region of } X\\
&NEG_R(X)=U-\overline{R}X,R\text{-negative region of } X\\
&BN_R(X) - R\text{-borderline region of } X\\
\end{align*}

If \(x\in POS(X)\), then \(x\) will be called an \(R\textbf{-positive}\) \textbf{example of} \(X\)

\begin{proposition}
\begin{enumerate}
\item $X$ is $R$-definable if and only if $\underline{R}X=\overline{R}X$
\item $X$ is rought w.r.t. $R$ if and only if $\underline{R}X\neq\overline{R}X$
\end{enumerate}
\end{proposition}
\subsection{Properties of approximations}
\label{sec:orgfbac266}
\begin{proposition}[2.2]
\begin{enumerate}
\item \(\uR X\subseteq X\subseteq \oR X\)
\item \(\uR\emptyset=\uR\emptyset=\emptyset;\quad \uR U=\oR U=U\)
\item \(\oR(X\cup Y)=\oR X\cup \oR Y\)
\item \(\uR(X\cap Y)=\uR X\cap \uR Y\)
\item \(X\subseteq Y\) implies \(\uR X\subseteq \uR Y\)
\item \(X\subseteq Y\) implies \(\oR X\subseteq\oR Y\)
\item \(\uR(X\cup Y)\subseteq \uR X\cup \uR Y\)
\item \(\uR(-X)=-\oR X\)
\item \(\oR(-X)=-\uR X\)
\item \(\oR(-X)=-\uR X\)
\item \(\uR\uR X=\oR\uR X=\uR X\)
\item \(\oR\oR X=\uR\oR X=\oR X\)
\end{enumerate}
\end{proposition}

The equivalence relation \(R\) over \(U\) uniquely defines a topological space
\(T=(U,DIS(R))\) where \(DIS(R)\) is the familty of all open and closed set in
\(T\) and \(U/R\) is a base for \(T\). The \(R\text{-lower}\) and \(R\text{-upper}\)
approximation of \(X\) in \(A\) are \textbf{interior} and \textbf{closure} operations in the
topological space \(T\)
\subsection{Approximations and membership relation}
\label{sec:orgbcea23d}
\begin{align*}
&x\underline{\in}_RX \text{if and only if } x\in\underline{R}X\\
&x\overline{\in}_RX \text{if and only if } x\in\overline{R}X\\
\end{align*}
where \(\underline{\in}_R\) read "\(x\) \textbf{surely belongs} to \(X\) w.r.t. \(R\)" and
\(\overline{\in}_R\) - "\(x\) \textbf{possibly belongs} to \(X\) w.r.t. \(R\)". The \textbf{lower} and
\textbf{upper} membership.
\begin{proposition}
\begin{enumerate}
\item $x\uin X$ implies $x\in X$ implies $x\oin X$
\item $X\subset Y$ implies ($x\uin X$ implies $x\uin Y$ and $x\oin X$ implies $x\oin Y$)
\item $x\oin(X\cup Y)$ if and only if $x\oin X$ or $x\oin Y$
\item $x\uin(X\cap Y)$ if and only if $x\uin X$ and $x\uin Y$
\item $x\uin X$ or $x\uin Y$ implies $x\uin (X\cup Y)$
\item $x\oin X\cap Y$ implies $x\oin X$ and $x\oin Y$
\item $x\uin (-X)$ if and only if non $x\oin X$
\item $x\oin (-X)$ if and only if non $x\uin X$
\end{enumerate}
\end{proposition}
\subsection{Numerical characterization of imprecision}
\label{sec:org0decbeb}
\textbf{accuracy measure}
\begin{equation*}
\alpha_R(X)=\frac{card\;\uR}{card\;\oR}
\end{equation*}
\subsection{Topological characterization of imprecision}
\label{sec:org4b190c3}
\begin{definition}[]
\begin{enumerate}
\item If \(\uR X\neq\emptyset\) and \(\oR X\neq U\), then we say that \(X\) is
\textbf{roughly R-definable}. We can decide whether some elements belong to \(X\)
or \(-X\)
\item If \(\uR X=\emptyset\) and \(\oR X\neq U\), then we say that \(X\) is
\textbf{internally R-undefinable}. We can decide whether some elemnts belong
to \(-X\)
\item If \(\uR X\neq\emptyset\) and \(\oR X=U\), then we say that \(X\) is
\textbf{externally R-undefinable}. We can decide whether some elements belong
to \(X\)
\item If \(\uR X=\emptyset\) and \(\oR X=U\), then we say that \(X\) is
\textbf{totally R-undefinable}. unable to decide
\end{enumerate}
\end{definition}

\begin{proposition}[2.4]
\begin{enumerate}
\item Set \(X\) is R-definable(roughly R-definable, totally R-undefinable) if and
only if so is \(-X\)
\item Set \(X\) is externally R-undefinable if and only if \(-X\) is internally
R-undefinable
\end{enumerate}
\end{proposition}

\begin{proof}
\begin{enumerate}
\item \begin{align*}
R\text{-definable}&\Leftrightarrow \uR X=\oR X, \uR\neq\emptyset,\oR\neq U\\
&\Leftrightarrow -\uR X=-\oR X\\
&\Leftrightarrow \oR(-X)=\uR(-X)\\
\end{align*}

\begin{align*}
X \text{ is roughly } R\text{-definable}
&\Leftrightarrow \uR X\neq \emptyset\wedge\oR X\neq U\\
&\Leftrightarrow -\uR X\neq U\wedge -\oR X\neq \emptyset\\
&\Leftrightarrow \oR(-X)\neq U\wedge \uR(-X)\neq \emptyset\\
\end{align*}
\end{enumerate}
\end{proof}
\subsection{Approximation of classifications}
\label{sec:org060f54d}
If \(F=\lb X_1,\dots,X_n\rb\) is a family of non empty sets, then
\(\uR F=\lb \uR X_1,\dots,\uR X_n\rb\) and \(\oR F=\lb\oR X_1,\dots,\oR X_n\rb\),
called the \(R\textbf{-lower}\) \textbf{approximation} and the \(R\textbf{-upper}\)
\textbf{approximation} of the family \(F\)

The \textbf{accuracy of approximation} of \(F\) by \(R\) is
\begin{equation*}
\alpha_R(F)=\frac{\displaystyle\sum card\;\uR X_i}
{\displaystyle\sum card\;\oR X_i}
\end{equation*}

\textbf{quality of approximation} of \(F\) by \(R\)
\begin{equation*}
\gamma_R(F)=\frac{\displaystyle\sum card\;\uR X_i}{card\; U}
\end{equation*}

\begin{proposition}[2.5]
Let \(F=\lb X_1,\dots,X_n\rb\) where \(n>1\) be a classification of \(U\) and let
\(R\) be an equivalence relation. If there exists \(i\in\lb 1,2,\dots,n\rb\) s.t.
\(\uR X_i\neq\emptyset\), then for each \(j\neq i\) and \(j\in\lb 1,\dots,n\rb\),
\(\oR X_j\neq U\)
\end{proposition}

\begin{proof}
If \(\uR X_i\neq\emptyset\) then there exists \(x\in X\) s.t. \([x]_R\subseteq X\),
which implies \([x]_R\cap X_j=\emptyset\) for each \(j\neq i\). This yields \(\oR
   X_j\cap[x]_R=\emptyset\).
\end{proof}

\begin{proposition}[2.6]
Let \(F=\lb X_1,\dots,X_n\rb,n>1\) be a classification of \(U\) and let \(R\) be an
equivalence relation. If there exists \(i\in\lb 1,\dots,n\rb\) s.t. \(\oR
   X_i=U\), then for each \(j\neq i\) and \(j\in\lb 1,\dots,n\rb\) \(\uR X_j=\emptyset\)
\end{proposition}

\begin{proposition}[2.7]
Let \(F=\lb X_1,\dots,X_n\rb,n>1\) be a classification of \(U\) and let \(R\) be an
equivalence relation. If for each \(i\in\lb 1,2,\dots,n\rb\) \(\uR
   X_i\neq\emptyset\) holds, then \(\oR X_i\neq U\) for each \(i\in\lb 1,\dots,n,\rb\)
\end{proposition}

\begin{proposition}[]
Let \(F=\lb X_1,\dots,X_n\rb,n>1\) be a classification of \(U\) and let \(R\) be an
equivalence relation. If for each \(i\in\lb 1,2,\dots,n\rb\) \(\oR X_i=U\) holds,
then \(\uR X_i=\emptyset\) for each \(i\in\lb 1,\dots,n\rb\)
\end{proposition}
\subsection{Rough equality of sets}
\label{sec:orge5c7952}
\begin{definition}[]
Let \(K=(U,\bR)\) be a knowledge base, \(X,Y\subseteq U\) and \(R\in IND(K)\), then
\begin{enumerate}
\item Sets \(X\) and \(Y\) are \textbf{bottom} \(R\textbf{-equal}\) \((X\eqsim_R Y)\) if \(\uR X=\uR
      Y\)
\item Sets \(X\) and \(Y\) are \textbf{top} \(R-\textbf{equal}\) \((X\simeq_R Y)\) if \(\oR X=\oR
      Y\)
\item Sets \(X\) and \(Y\) are \(R\textbf{-equal}\) \((X\approx_R Y)\) if \(X\simeq_R Y\)
and \(X\eqsim_R Y\)
\end{enumerate}
\end{definition}

\begin{proposition}[2.9]
\begin{enumerate}
\item \(X\eqsim Y\) iff \(X\cap Y\eqsim X\) and \(X\cap Y\eqsim Y\)
\item \(X\simeq Y\) iff \(X\cup Y\simeq X\) and \(X\cup Y\simeq Y\)
\item If \(X\simeq X'\) and \(Y\simeq Y'\) then \(X\cup Y\simeq X'\cup Y'\)
\item If \(X\eqsim X'\) and \(Y\eqsim Y'\) then \(X\cap Y\eqsim X'\cap Y'\)
\item If \(X\simeq Y\), then \(X\cup -Y\simeq U\)
\item If \(X\eqsim Y\), then \(X\cap -Y\eqsim\emptyset\)
\item If \(X\subseteq Y\) and \(Y\simeq\emptyset\), then \(X\simeq\emptyset\)
\item If \(X\subseteq Y\) and \(X\subseteq U\) then \(Y\subseteq U\)
\item \(X\simeq Y\) iff \(-X\eqsim -Y\)
\item If \(X\eqsim \emptyset\) or \(Y\eqsim\emptyset\), then \(X\cap
       Y\eqsim\emptyset\)
\item If \(X\simeq U\) or \(Y\simeq U\), then \(X\cup Y\simeq U\)
\end{enumerate}
\end{proposition}

\begin{proposition}[2.10 ]
For any equivalence relation \(R\)
\begin{enumerate}
\item \(\uR X\) is the intersection of all \(Y\subseteq U\) s.t. \(X\eqsim_R Y\)
\item \(\oR\) is the union of all \(Y\subseteq U\) s.t. \(X\simeq_R Y\)
\end{enumerate}
\end{proposition}
\subsection{Rough inclusion of sets}
\label{sec:orgc37aac6}
\begin{definition}[]
Let \(K=(U,\bR)\) be a knowledge base, \(X,Y\subseteq U\) and \(R\in IND(K)\).
\begin{enumerate}
\item Set \(X\) is \textbf{bottom} \(R\textbf{-included}\) in \(Y\) \((X\subsetsim_R  Y)\) iff \(\uR
      X\subseteq\uR Y\)
\item Set \(X\) is \textbf{top} \(R\textbf{-included}\) in \(Y\) \((X\simsubset_R Y)\) iff \(\oR
      X\subseteq \oR Y\)
\item Set \(X\) is \(R\textbf{-included}\) in \(Y\) \((X\simsubsetsim_R Y)\) iff
\(X\simsubset_R Y\) and \(X\subsetsim_R Y\)
\end{enumerate}
\end{definition}

\begin{proposition}[2.11]
\begin{enumerate}
\item If \(X\subseteq Y\), then \(X\subsetsim Y, X\simsubset Y\) and \(X\simsubsetsim
      Y\)
\item If \(X\subsetsim Y\) and \(Y\subsetsim X\), then \(X\eqsim Y\)
\item If \(X\simsubset Y\) and \(Y\simsubset X\), then \(X\simeq Y\)
\item If \(X\simsubsetsim Y\) and \(Y\simsubsetsim X\) then \(X\approx Y\)
\item \(X\simsubset Y\) iff \(X\cup Y\simeq Y\)
\item \(X\subsetsim Y\) iff \(X\cap Y\eqsim X\)
\item If \(X\subseteq Y, X\eqsim X',Y\eqsim Y'\), then \(X'\subsetsim Y'\)
\item If \(X\subseteq Y, X\simeq X',Y\simeq Y'\), then \(X'\simsubset Y'\)
\item If \(X\subseteq Y, X\approx X',Y\approx Y'\), then \(X'\simsubsetsim Y'\)
\item If \(X'\simsubset X\) and \(Y'\simsubset Y\), then \(X'\cup Y'\simsubset X\cup
       Y\)
\item If \(X'\subsetsim X,Y'\subsetsim\) then \(X'\cap Y'\subsetsim X\cap Y\)
\item \(X\cap Y\subsetsim X\simsubset X\cup Y\)
\item If \(X\subsetsim Y\) and \(X\eqsim Z\) then \(Z\subsetsim Y\)
\item If \(X\simsubset Y\) and \(X\simeq Z\) then \(Z\simsubset Y\)
\item If \(X\simsubsetsim Y\) and \(X\approx\) then \(Z\simsubsetsim Y\)
\end{enumerate}
\end{proposition}
\section{Reduction of knowledge}
\label{sec:orgc0d3bee}
\subsection{Reduct and Core of Knowledge}
\label{sec:orgbb88edf}
Let \(\bR\) be a family of equivalence relations and let \(P\in\bR\). \(R\) is
\textbf{dispensable} in \(\bR\) if \(IND(\bR)=IND(\bR-\lb R\rb)\). Otherwise \(R\) is
\textbf{indispensable} in \(\bR\). The family of \(\bR\) is \textbf{independent} if each \(R\in\bR\)
is indispensable in \(\bR\). Otherwise \(\bR\) is \textbf{dependent}

\begin{proposition}[3.1]
If \(\bR\) is independent and \(\bP\subseteq \bR\), then \(\bP\) is also independent
\end{proposition}

\begin{proof}
\(IND(\bR)=IND(\bP\cup(\bR-\bP))=IND(\bP)\cap IND(\bR-\bP)\)
\end{proof}

\(\bQ\subseteq \bR\) is a \textbf{reduct} of \(\bP\) if \(\bQ\) is independent and
\(IND(\bQ)=IND(\bP)\)


The set of all indispensable relations in \(\bP\) is called the \textbf{core} of \(\bP\)
denoted by \(CORE(\bP)\)

\begin{proposition}[3.2]
\begin{equation*}
CORE(\bP)=\bigcap RED(\bP)
\end{equation*}
where \(RED(\bP)\) is the family of all reducts of \(\bP\)
\end{proposition}

\begin{proof}
If \(\bQ\) is a reduct of \(\bP\) and \(R\in\bP-\bQ\), then \(IND(\bP)=IND(\bQ)\). If
\(\bQ\subseteq\bR\subseteq\bP\) then \(IND(\bQ)=IND(\bR)\). Assuming \(\bR=\bP-\lb
   R\rb\) then \(R\notin CORE(\bP)\)

If \(R\notin CORE(\bP)\). This means \(IND(\bP)=IND(\bP-\lb R\rb)\) which implies
that there exists an independent subset \(\bS\subseteq \bP-\lb R\rb\) s.t.
\(IND(\bS)=IND(\bP)\). Hence \(R\notin\bigcap RED(\bP)\)
\end{proof}
\subsection{Relative reduct and relative core of knowledge}
\label{sec:org8868af9}
Let \(P\) and \(Q\) be equivalence relations over \(U\)

\(P\textbf{-positive}\)
\begin{equation*}
POS_P(Q)=\displaystyle\bigcup_{X\in U/Q}\uP X
\end{equation*}
The \(P\text{-positive}\) region of \(Q\) is the set of all objects of the
universe \(U\) which can be properly classified to classes of \(U/Q\) employing
knowledge expressed by the classification \(U/P\)


Let \(\bP\) and \(\bQ\) be families of equivalence relations over \(U\)

\(R\in\bP\) is \(\bQ\textbf{-dispensable}\) in \(\bP\) if
\begin{equation*}
POS_{IND(\bP)}(IND(\bQ))=POS_{IND(\bP-\lb R\rb)}(IND(\bQ))
\end{equation*}
otherwise \(R\) is \(\bQ\text{-indispensable}\) in \(\bP\)

If every \(R\) in \(\bP\) is \(\bQ\text{-indispensable}\), we will say that \(\bP\)
is \(\bQ\textbf{-independent}\) or \(\bP\) is \textbf{independent w.r.t.} \(\bQ\)

The family \(\bS\subseteq \bP\) will be called a \(\bQ\textbf{-reduct}\) of \(\bP\)
if and only if \(\bS\) is the \(\bQ\text{-independent}\) subfamily of \(\bP\) and
\(POS_{\bS}(\bQ)=POS_{\bP}(\bQ)\)

The set of all \(\bQ\text{-indispensable}\) elmentary relations in \(\bP\) will
be called the \(\bQ\textbf{-core}\) of \(\bP\) and will be denoted as
\(CORE_{\bQ}(\bP)\)


\begin{proposition}[3.3]
\begin{equation*}
CORE_{\bQ}(\bP)=\bigcap RED_{\bQ}(\bP)
\end{equation*}
where \(RED_{\bQ}(\bP)\) is the family of all \(\bQ\text{-reducts}\) of \(\bP\)
\end{proposition}
\subsection{Reduction of categories}
\label{sec:org9de3057}
Basic categories are pieces of knowledge, which can be considered as
"building blocks" of concepts. Every concept in the knowledge base can be
only expressed (exactly or approximately) in terms of basic categories. On
the other hand, every  basic category is "built up" (is an intersection) of
some elementary categories. Thus the question arises whether all the
elementary categories are necessary to define the basic categories in
question. 

Let \(F=\lb X_1,\dots,X_n\rb\) be a family of sets s.t. \(X_i\subseteq U\).

\(X_i\) is \textbf{dispensable} in \(F\) if \(\bigcap(F-\lb X_i\rb)=\bigcap F\), otherwise
the set \(X_i\) is \textbf{indispensable} in \(F\)

The family \(F\) is \textbf{independent} if all of its components are indispensable in
\(F\). Otherwise \(F\) is \textbf{dependent}

The family \(H\subseteq F\) is a \textbf{reduct} of \(F\) if \(H\) is independent and
\(\bigcap H=\bigcap F\)

The family of all indispensable sets in \(F\) will be called the \textbf{core} of \(F\),
denoted \(CORE(F)\)

\begin{proposition}[3.4]
\begin{equation*}
CORE(F)=\bigcap RED(F)
\end{equation*}
\end{proposition}
\subsection{Relative reduct and core of categories}
\label{sec:orgcc350cb}
\(F=\lb X_1,\dots,X_n\rb,X_i\subseteq U\) and a subset \(Y\subseteq U\) s.t.
\(\bigcap F\subseteq Y\)

\(X_i\) is \(Y\textbf{-dispensable}\) in \(\bigcap F\) if \(\bigcap(F-\lb
   X_i\rb)\subseteq Y\). Otherwise \(X_i\) is \(Y\textbf{-indispensable}\)

The family \(F\) is \(Y\textbf{-independent}\) in \(\bigcap F\) if all of its
components are \(Y\textbf{-indispensable}\) in \(\bigcap F\)

The family \(H\subseteq F\) is a \(Y\textbf{-reduct}\) of \(\bigcap F\) if \(H\) is
\(Y\text{-independent}\) in \(\bigcap F\) and \(\bigcap H\subseteq Y\)

The family of all \(Y\text{-indispensable}\) sets in \(\bigcap F\) will be called
the \(Y\textbf{core}\) of \(F\) and will be denoted by \(CORE_Y(F)\)

\begin{proposition}[3.5]
\begin{equation*}
CORE_Y(F)=\bigcap RED_Y(F)
\end{equation*}
\end{proposition}

\section{Dependencies in knowledge base}
\label{sec:org022066d}
\subsection{Dependency of knowledge}
\label{sec:orgabcc16f}
Knowledge \(\bQ\) is \textbf{derivable} from knowledge \(\bP\) if all elementary
categories of \(\bQ\) can be defined in terms of some elementary categories of
knowledge \(\bP\). If \(\bQ\) is derivable from \(\bP\) we will also say that \(\bQ\)
\textbf{depends} on \(\bP\) and can be written \(\bP\Rightarrow \bQ\)

Let \(K=(U,\bR)\) be a knowledge base and let \(\bP,\bQ\subseteq \bR\)
\begin{enumerate}
\item Knowledge \(\bQ\) \textbf{depends on knowledge} \(\bP\) iff \(IND(\bP)\subseteq
      IND(\bQ)\) note that \(IND(\bP)\) is a set of pair
\item Knowledge \(\bP\) and \(\bQ\) are \textbf{equivalent} denoted as \(\bP\equiv\bQ\) iff
\(\bP\Rightarrow\bQ\) and \(\bQ\Rightarrow\bP\)
\item Knowledge \(\bP\) and \(\bQ\) are \textbf{independent} denoted as \(\bP\not\equiv\bQ\)
iff neither \(\bP\Rightarrow\bQ\) nor \(\bQ\Rightarrow\bP\)
\end{enumerate}


Obiviously \(\bP\equiv\bQ\) if and only if \(IND(\bP)=IND(\bQ)\)


\begin{proposition}[4.1]
The following conditions are equivalent
\begin{enumerate}
\item \(\bP\Rightarrow\bQ\)
\item \(IND(\bP\cup\bQ)=IND(\bP)\)
\item \(POS_{\bP}(\bQ)=POS_{IND(\bP)}(\bQ)=U\)
\item \(\underline{\bP} X=X\) for all \(X\in U/Q\)
\end{enumerate}


where \(\underline{\bP} X\) denotes \(\underline{IND(\bP)} X\)
\end{proposition}
\begin{proposition}[4.2]
If \(\bP\) is a reduct of \(\bQ\) then \(\bP\Rightarrow \bQ-\bP\) and \(IND(\bP)=IND(\bQ)\)
\end{proposition}

\begin{proof}
\begin{enumerate}
\item \((1)\to (2)\)

\(IND(\bP)\subseteq IND(\bP\cup \bQ)\subseteq IND(\bP)\)
\item \((2)\to (3)\)
\begin{align*}
POS_{IND(\bP)}(\bQ)&=\displaystyle\bigcup_{X\in U/\bQ} 
\underline{IND(\bP)} X\\
&=\displaystyle\bigcup_{X\in U/\bQ} \underline{IND(\bP\cup \bQ)} X
\end{align*}
Since \(\bQ\subseteq \bP\cup\bQ\), \(IND(\bP\cup\bQ)\subseteq IND(\bQ)\) and
for each \(x\in U\), \([x]_{IND(\bP\cup\bQ)}\subseteq [x]_{IND(\bQ)}\), which
means for any \(Y\in U/\bP\cup\bQ\), there exists some \(X\in U/\bQ\) s.t.
\(Y\subseteq X\). Hence \(POS_{\bP}(\bQ)=U\)
\item \((3)\to(4)\)
\begin{align*}
POS_{\bP}(\bQ)&=\displaystyle\bigcup_{X\in U/\bQ}\underline{IND(\bP)} X\\
&=\displaystyle\bigcup_{X\in U/bQ}\underline{\bP} X=U\\
\end{align*}
And \(\underline{\bP} X\subseteq X\)
\item \((4)\to (1)\)
\begin{align*}
\bP\Rightarrow\bQ&\Leftrightarrow IND(\bP)\subseteq IND(\bQ)\\
&\Leftrightarrow \forall x\in U, [x]_{IND(\bP)}\subseteq [x]_{IND(\bQ)}\\
\end{align*}
\end{enumerate}
\end{proof}

\begin{proof}
\(\bP\Rightarrow\bQ-\bP\Leftrightarrow IND(\bP\cup\bQ-\bP)=IND(\bP)\)
\end{proof}

\begin{proposition}[4.3]
\begin{enumerate}
\item If \(\bP\) is dependent, then there exists a subset \(\bQ\subset \bP\) s.t.
\(\bQ\) is a reduct of \(\bP\)
\item If \(\bP\subseteq\bQ\) and \(\bP\) is dependent, then all basic relations in
\(\bP\) are pairwise independent
\item If \(\bP\subseteq\bQ\) and \(\bP\) is independent, then every subset \(\bR\) of
\(\bP\) is independent
\end{enumerate}
\end{proposition}

\begin{proposition}[4.4]
\begin{enumerate}
\item If \(\bP\Rightarrow\bQ\) and \(\bP'\supset\bP\), then \(\bP'\Rightarrow\bQ\)
\item If \(\bP\Ra\bQ\) and \(\bQ'\subset\bQ\) then \(\bP\Ra\bQ'\)
\item \(\bP\Ra\bQ\) and \(\bQ\Ra\bR\) imply \(\bP\Ra\bR\)
\item \(\bP\Ra\bR\) and \(\bQ\Ra\bR\) imply \(\bP\cup\bQ\Ra\bR\)
\item \(\bP\Ra\bR\cup\bQ\) implies \(\bP\Ra\bR\) and \(\bP\Ra\bQ\)
\item \(\bP\Ra\bQ\) and \(\bR\Ra\bT\) imply \(\bP\cup\bR\Ra\bQ\cup\bT\)
\item \(\bP\Ra\bQ\) and \(\bR\Ra\bT\) imply \(\bP\cup\bR\Ra\bQ\cup\bT\)
\end{enumerate}
\end{proposition}
\subsection{Partial dependency of knowledge}
\label{sec:orgc4dcf96}
Let \(K=(U,\bR)\) be the knowledge base and \(\bP,\bQ\subset \bR\). Knowledge
\(\bQ\) \textbf{depends in a degree} \(k(0\le k \le 1)\) from knowledge \(\bP\),
symbolically \(\bP\Ra_k\bQ\) if and only if
\begin{equation*}
k=\gamma_{\bP}(\bQ)=\frac{card\; POS_{\bP}(\bQ)}{card\; U}
\end{equation*}

If \(k=1\), \(\bQ\) \textbf{totally depends from} \(\bP\). If \(0<k<1\), \(\bQ\) \textbf{roughly}
\textbf{depends from} \(\bP\). If \(k=0\), \(\bQ\) is \textbf{totally independent from} \(\bP\)

Ability to classify objects.
\begin{proposition}[4.5]
\begin{enumerate}
\item If \(\bR\Ra_k\bP\) and \(\bQ\Ra_l\bP\), then \(\bR\cup\bQ\Ra\bP\) for some
\(m\ge\max(k,l)\)
\item If \(\bR\cup\bP\Ra_k\bQ\), then \(\bR\Ra_l\bQ\) and \(\bP\Ra_m\bQ\) for some
\(l,m\le k\)
\item If \(\bR\Ra_k\bQ\) and \(\bR\Ra_l\bP\) then \(\bR\Ra_m\bQ\cup\bP\) for some
\(m\le\min(k,l)\)
\item If \(\bR\Ra_k\bQ\cup\bP\) then \(\bR\Ra_l\bQ\) and \(\bR\Ra_m\bP\) for some 
\(l,m\ge k\)
\item If \(\bR\Ra_k\bP\) and \(\bP\Ra_l\bQ\) then \(\bR\Ra_m\bQ\) for some \(m\ge l+k-1\)
\end{enumerate}
\end{proposition}
\section{Knowledege prepresentation}
\label{sec:orgd4ef235}
\subsection{Formal definition}
\label{sec:orga28668e}
\textbf{Knowledge representation system} is a pair \(S=(U,A)\) where \(U\) is a nonempty
finite set called the \textbf{universe}, and \(A\) is a nonempty finite set of
\textbf{primitive attributes}

Every primitive attribute \(a\in A\) is a total function \(a:U\to V_a\) where
\(V_a\) is the \textbf{domain} of \(a\)

With every subset of attributes \(B\subseteq A\) we associate a binary relation
\(IND(B)\) called and \textbf{indiscernibility relation}
\begin{equation*}
IND(B)=\lb(x,y)\in U^2:\text{for every } a\in B,a(x)=a(y)\rb
\end{equation*}
\(IND(B)\) is an euivalence relation and
\begin{equation*}
IND(B)=\displaystyle\bigcap_{a\in B} IND(a)
\end{equation*}

Every subset \(B\subseteq A\) will be called an \textbf{attribute}. If \(B\) is a single
element set, then \(B\) is called \textbf{primitive} otherwise \textbf{compound}

\(a(x)\) can be viewed as a name of \([x]_{IND(a)}\). The name of an elementary
category of attribute \(B\subseteq A\) containing object \(x\) is a set of pairs
\(\lb a,a(x):a\in B\rb\)

There is a one-to-one correspondence between knowledge bases and knowledge
representation system up to isomorphism of attributes and attribute names

Suppose

\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 2 & 0\\
2 & 0 & 1 & 1 & 1 & 2\\
3 & 2 & 0 & 0 & 1 & 1\\
4 & 1 & 1 & 0 & 2 & 2\\
5 & 1 & 0 & 2 & 0 & 1\\
6 & 2 & 2 & 0 & 1 & 1\\
7 & 2 & 1 & 1 & 1 & 2\\
8 & 0 & 1 & 1 & 0 & 1\\
\end{tabular}
\end{center}

The universe \(U=\{1,2,3,4,5,6,7,8\}\). \(V=V_a=\dots=V_e=\{0,1,2\}\)
\begin{align*}
&U/IND\{a\}=\{\{2,8\},\{1,4,5\},\{3,6,7\}\}\\
&U/IND\{c,d\}=\{\{1\},\{3,6\},\{2,7\},\{4\},\{5\},\{8\}\}
\end{align*}
\subsection{Discernibility matrix}
\label{sec:orgdf8198c}
Let \(S=(U,A)\) be a knowledge representation system with \(U=\lb
   x_1,x_2,\dots,x_n\rb\). By an \textbf{discernibility matrix of} \(S\) is
\begin{equation*}
M(S)=(c_{ij})=\lb a\in A:a(x_i)\neq a(x_j)\rb \quad\text{for } i,j=1,2,\dots,n
\end{equation*}

Now the core can be defined as the set of all single element entries of the
discernibility matrix

\(B\subseteq A\) is the reduct of \(A\) if \(B\) is the minimal subset of A s.t.
\begin{equation*}
B\cap c\neq\emptyset \text{ for any nonempty entry } c(c\neq\emptyset) \text{ in }
M(S)
\end{equation*}
\section{Decision tables}
\label{sec:org13fdddf}
\subsection{Formal definition and some properties}
\label{sec:org4b424a3}
Let \(K=(U,A)\) be a knowledge representation system and let \(C,D\subset A\) be
two subsets of attributes called \textbf{condition} and \textbf{decision attributes}
repectively. KR-system with distinguished condition ad decision attributes
will be called a \textbf{decision table} and will be denoted by \(T=(U,A,C,D)\) or in
short \(CD\)

Equivalence classes of the relations \(IND(C)\) and \(IND(D)\) will be called
\textbf{condition} and \textbf{decision classes}

With every \(x\in U\) we associate a function \(d_x:A\to V\) s.t. \(d_x(a)=a(x)\)
for every \(a\in C\cup D\). The function \(d_x\) will be called a \textbf{decision rule}

If \(d_x\) is a decision rule, then the restriction of \(d_x\) to C, denoted
\(d_x|C\) and the restriction of \(d_x\) to \(D\), denoted \(d_x|D\) will be called
\textbf{conditions} and \textbf{decisions} of \(d_x\)

The decision rule \(d_x\) is \textbf{consistent} if for every \(y\neq x,d_x|C=d_y|C\)
implies \(d_x|D=d_y|D\). Otherwise \textbf{inconsistent}

A decision table is \textbf{consistent} if al its decision rules are consistent

\begin{proposition}[6.1]
A decision table \(T=(U,A,C,D)\) is consistent if and only if \(C\Ra D\)
\end{proposition}

\begin{proposition}[6.2]
Each decision table \(T=(U,A,C,D)\) can be uniquely decomposed into two
decision tables \(T_1=(U,A,C,D)\) and \(T_2=(U,A,C,D)\) s.t. \(C\Ra_1 D\) in \(T_1\)
and \(C\Ra_0 D\) in \(T_2\) where \(U_1=POS_{C}(D)\) and 
\(U_2=\displaystyle\bigcup_{X\in U/IND(D)}BN_C(X)\)
\end{proposition}

Example. Consider
\begin{table}[htbp]
\caption{\label{tab:dec-tab-1}
Knowledge representation system}
\centering
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 2 & 0\\
2 & 0 & 1 & 1 & 1 & 2\\
3 & 2 & 0 & 0 & 1 & 1\\
4 & 1 & 1 & 0 & 2 & 2\\
5 & 1 & 0 & 2 & 0 & 1\\
6 & 2 & 2 & 0 & 1 & 1\\
7 & 2 & 1 & 1 & 1 & 2\\
8 & 0 & 1 & 1 & 0 & 1\\
\end{tabular}
\end{table}

Assume that a,b,c are condition attributes and d,e are decision attributes. 
\begin{align*}
  &U/\{a\}=\{\{2,8\},\{1,4,5\},\{3,6,7\}\}\\
  &U/\{b\}=\{\{1,3,5\},\{2,4,7,8\},\{6\}\}\\
  &U/\{c\}=\{\{3,4,6\},\{2,7,8\},\{1,5\}\}\\
  &U/\{d\}=\{\{5,8\},\{2,3,6,7\},\{1,4\}\}\\
  &U/\{e\}=\{\{1\},\{3,5,6,8\},\{2,4,7\}\}\\
  &U/\{a,b,c\}=\{\{1,5\},\{2,8\},\{3\},\{4\},\{6\},\{7\}\}\\
  &U/\{d,e\}=\{\{1\},\{2,7\},\{3,6\},\{4\},\{5,8\}\}\\
  &POS_C(D)=\{3,4,6,7\}\\
  &\displaystyle\bigcup_{X\in/IND(D)}BN_C(X)=\{1,2,5,8\}\\
\end{align*}

\begin{table}[htbp]
\caption{\label{tab:dec-tab-2}
}
\centering
\begin{tabular}{rrrrrr}
\(U_1\) & a & b & c & d & e\\
\hline
3 & 2 & 0 & 0 & 1 & 1\\
4 & 1 & 1 & 0 & 2 & 2\\
6 & 2 & 2 & 0 & 1 & 1\\
7 & 2 & 1 & 1 & 1 & 2\\
\end{tabular}
\end{table}

\begin{table}[htbp]
\caption{\label{tab:dec-tab-3}
}
\centering
\begin{tabular}{rrrrrr}
\(U_2\) & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 2 & 0\\
2 & 0 & 1 & 1 & 1 & 2\\
5 & 1 & 0 & 2 & 0 & 1\\
8 & 0 & 1 & 1 & 0 & 1\\
\end{tabular}
\end{table}

Table \ref{tab:dec-tab-2} is consistent whereas table \ref{tab:dec-tab-3} is totally inconsistent
\subsection{Simplification of decision tables}
\label{sec:orgbe60f18}
Step
\begin{enumerate}
\item Computation of reducts of condition attributes which is equivalent to
elimination of some column from the decision table
\item elimination of duplicate rows
\item elimination of superfluous values of attributes
\end{enumerate}


Thus the proposed method consists in removing superfluous condition
attributes (columns), duplicate rows and, in addition to that, irrelevant
values of condition attributes.


Suppose \(B\subseteq A\) and an object \(x\). \(\forall C,
   [x]_C=\displaystyle\bigcup_{a\in C}[x]_a\). Each \([x]_a\) is uniquely determined by
attribute value \(a(x)\). hence in order to remove superfluous values of
condition attributes, we have to eliminate all superfluous equivalence
classes \([x]_a\) from the equivalence class \([x]_C\) 

Given 
\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 0 & 1 & 1\\
2 & 1 & 0 & 0 & 0 & 1\\
3 & 0 & 0 & 0 & 0 & 0\\
4 & 1 & 1 & 0 & 1 & 0\\
5 & 1 & 1 & 0 & 2 & 2\\
6 & 2 & 1 & 0 & 2 & 2\\
7 & 2 & 2 & 2 & 2 & 2\\
\end{tabular}
\end{center}
where a,b,c,d are condition attributes and e is a decision attribute.

e-dispensable condition attribute is c and we can remove it
\begin{center}
\begin{tabular}{rrrrr}
U & a & b & d & e\\
\hline
1 & 1 & 0 & 1 & 1\\
2 & 1 & 0 & 0 & 1\\
3 & 0 & 0 & 0 & 0\\
4 & 1 & 1 & 1 & 0\\
5 & 1 & 1 & 2 & 2\\
6 & 2 & 1 & 2 & 2\\
7 & 2 & 2 & 2 & 2\\
\end{tabular}
\end{center}
Next we need to reduce superfluous values of condition attributes. First
compute core values of condition attributes

First compute the core values of condition attributes for the first decision
rule, i.e. the core of the family of sets
\begin{equation*}
\bF=\lb[1]_a,[1]_b,[1]_d\rb=\lb\lb 1,2,3,4\rb,\lb 1,2,3\rb,\lb 1,4\rb\rb
\end{equation*}
is 
\begin{equation*}
[1]_{\lb a,b,d\rb}=[1]_a\cap [1]_b\cap[1]_d=\lb 1\rb
\end{equation*}
Moreover \(a(1)=1,b(1)=0,d(1)=1\). In order to find dispensable categories, we
have to drop one category at a time and check whether the intersection of
remaining categories is still included in the decision category \([1]_e=\lb
   1,2\rb\)
\begin{align*}
  &[1]_b\cap[1]_d=\lb 1,2,3\rb\cap\lb 1,4\rb=\lb 1\rb\\
  &[1]_a\cap[1]_d=\lb 1,2,4,5\rb\cap\lb 1,4\rb=\lb 1,4\rb\\
  &[1]_a\cap[1]_b=\lb 1,2,4,5\rb\cap\lb 1,2,3\rb=\lb 1,2\rb\\
\end{align*}

\(a\) is dispensable. This means that the core value is \(b(1)=0\)

\begin{center}
\begin{tabular}{rlllr}
U & a & b & d & e\\
\hline
1 & - & 0 & - & 1\\
2 & 1 & - & - & 1\\
3 & 0 & - & - & 0\\
4 & - & 1 & 1 & 0\\
5 & - & - & 2 & 2\\
6 & - & - & - & 2\\
7 & - & - & - & 2\\
\end{tabular}
\end{center}

Having computed core values of condition attributes, we can proceed to
compute value reducts. 

Only \([1]_b \cap [1]_d\) and \([1]_a \cap [1]_b\) are reducts of the family \(\bF\).
Hence
\begin{center}
\begin{tabular}{ccccc}
U & a & b & d & e\\
\hline
1 & 1 & 0 & \texttimes{} & 1\\
1' & \texttimes{} & 0 & 1 & 1\\
2 & 1 & 0 & \texttimes{} & 1\\
2' & 1 & \texttimes{} & 0 & 1\\
3 & 0 & \texttimes{} & \texttimes{} & 0\\
4 & \texttimes{} & 1 & 1 & 0\\
5 & \texttimes{} & \texttimes{} & 2 & 2\\
6 & \texttimes{} & \texttimes{} & 2 & 2\\
6' & 2 & \texttimes{} & \texttimes{} & 2\\
7 & \texttimes{} & \texttimes{} & 2 & 2\\
7' & \texttimes{} & 2 & \texttimes{} & 2\\
7'' & 2 & \texttimes{} & \texttimes{} & 2\\
\end{tabular}
\end{center}

Note that
\begin{center}
\begin{tabular}{cllrr}
U & a & b & d & e\\
\hline
1 & 1 & 0 & \texttimes{} & 1\\
2 & 1 & 0 & \texttimes{} & 1\\
3 & 0 & \texttimes{} & \texttimes{} & 0\\
4 & \texttimes{} & 1 & 1 & 0\\
5 & \texttimes{} & \texttimes{} & 2 & 2\\
6 & \texttimes{} & \texttimes{} & 2 & 2\\
7 & \texttimes{} & \texttimes{} & 2 & 2\\
\end{tabular}
\end{center}
we have
\begin{center}
\begin{tabular}{clllr}
U & a & b & d & e\\
\hline
1,2 & 1 & 0 & \texttimes{} & 1\\
3 & 0 & \texttimes{} & \texttimes{} & 0\\
4 & \texttimes{} & 1 & 1 & 0\\
5,6,7 & \texttimes{} & \texttimes{} & 2 & 2\\
\end{tabular}
\end{center}
This solution is \textbf{minimal}
\section{Reasoning about knowledge}
\label{sec:orgb88ada7}
\subsection{The language of decision logic}
\label{sec:org3bb433c}
\textbf{alphabet} of the language
\begin{enumerate}
\item \(A\) - the set of \textbf{attribute constant}
\item \(V=\bigcup V_\alpha\), the set of \textbf{attribute value constants} \(\alpha\in A\)
\item Set \(\lb\sim,\wedge,\vee,\to,\equiv\rb\) of propositional connectives, called \textbf{negation} \ldots{}
\end{enumerate}


Set of formulas
\begin{enumerate}
\item Expressions of the form \((a,v)\) or in short \(a_v\) called \textbf{elementary
formulas} are formulas of the DL-language for any \(a\in A,v\in V_a\)
\item If \(\phi\) and \(\psi\) are formulas of the DL-language, then so are
\(\sim\phi\),(\(\phi \vee \psi\)),(\(\phi \wedge \psi\)),(\(\phi \to \psi\)) and (\(\phi \equiv \phi\))
\end{enumerate}
\subsection{Semantics of decision logic language}
\label{sec:org511499c}
atomic formula \((a,v)\) is interpreted as a description of all objects having
value \(v\) for attribute \(a\). By the model we mean the KR-system \(S=(U,A)\).
Thus the model \(S\) describes the meaning of symbols of predicates \((a,v)\) in \(U\)


An object \(x\in U\) \textbf{satisfies} a formula \(\phi\) in \(S=(U,A)\) denoted \(x\models_S\phi\)
or in short \(x\models\phi\) if and only if
\begin{enumerate}
\item \(x\models(a,v)\) iff \(a(x)=v\)
\item \(x\models\sim\phi\) iff \(x\not\models\phi\)
\item \(x\models\phi\vee\psi\) iff \(x\models\phi\) or \(x\models\psi\)
\item \(x\models\phi\vee\psi\) iff \(x\models\phi\) and \(x\models\psi\)
\end{enumerate}


As a corollary from the above conditions we get
\begin{enumerate}
\item \(x\models\phi\to\psi\) iff \(x\models\sim\phi\vee\psi\)
\item \(x\models\phi\equiv\psi\) iff \(x\models\phi\to\psi\) and \(x\models\psi\to\phi\)
\end{enumerate}


If \(\phi\) is a formula then the set \(\abs{\phi}_S\) is defined as
\begin{equation*}
\abs{\phi}_S=\lb x\in U:x\models_S\phi\rb
\end{equation*}
called the \textbf{meaning} of the formula \(\phi\) in \(S\)

\begin{proposition}[7.1]
\begin{enumerate}
\item \(\abs{(a,v)}_S=\lb x\in U:a(x)=v\rb\)
\item \(\abs{\sim\phi}_S=-\abs{\phi}_S\)
\item \(\abs{\phi\vee\psi}_S=\abs{\phi}_S\cup\abs{\psi}_S\)
\item \(\abs{\phi\wedge\psi}_S=\abs{\phi}_S \cup\abs{\psi}_S\)
\item \(\abs{\phi\to\psi}_S=-\abs{\phi}_S \cup\abs{\psi}_S\)
\item \(\abs{\phi\equiv\psi}_S=(\abs{\phi}_S \cap\abs{\psi}_S)\cup(-\abs{\phi}_S \cap-\abs{\psi}_S)\)
\end{enumerate}
\end{proposition}

A formula \(\phi\) is said to be \textbf{true} in a KR-system \(S\), \(\models_S\phi\) if and only
if \(\abs{\phi}_S=U\)

Formulas \(\phi\) and \(\psi\) are equivalent in \(S\) if and only if \(\abs{\phi}_S=\abs{\psi}_S\)

\begin{proposition}[7.2]
\begin{enumerate}
\item \(\models_S \phi\) iff \(\abs{\phi}_S=U\)
\item \(\models_S \sim\phi\) iff \(\abs{\phi}_S=\emptyset\)
\item \(\models_S \phi\to\psi\) iff \(\abs{\phi}_S \subseteq\abs{\psi}_S\)
\item \(\models_S \phi\equiv\psi\) iff \(\abs{\phi}_S=\abs{\psi}_S\)
\end{enumerate}
\end{proposition}
\subsection{Deduction in decision logic}
\label{sec:org71a2235}
In order to define our logic, we need to verify the semantic equivalence of
formulas. To do this we need to finish with suitable rules for transforming
formulas without changing their meanings.

Abbreviations:
\begin{equation*}
\phi\wedge\sim\phi=_{df} 0 \text{ and } \phi\vee\sim\phi=_{df} 1
\end{equation*}
Formula of the form
\begin{equation*}
(a_1, v_1)\wedge (a_2, v_2)\wedge\dots\wedge(a_n, v_n)
\end{equation*}
where \(v_i \in V_a, P=\lb a_1, \dots,a_n \rb\) and \(P\subseteq A\) will be called a
\(P\textbf{-basic formula}\) or in short \(P\textbf{-formula}\). \(A\text{-basic}\)
formulas will be called \textbf{basic formulas}

Let \(P\subseteq A\), \(\phi\) be a \(P\text{-formula}\) and \(x\in U\). If \(x\models\phi\),
then \(\phi\) will be called the \(P\textbf{-description}\) of \(x\) in \(S\). The set of
all \(A\text{-basic}\) formulas satisfiable in the knowledge representation
system \(S=(U,A)\) will be called the \textbf{basic knowledge} in \(S\). \(\sum_S(P)\) or in
short \(\sum(P)\) is the disjuntion of all \(P\text{-formulas}\) satisfied in \(S\).
If \(P=A\), then \(\sum(A)\) will be called the \textbf{characteristic formula} of the
KR-system.


Each row in the table is represented by a certain \(A\text{-formula}\) and the
whole table is now represented by the set of all such formulas

Consider
\begin{table}[htbp]
\caption{\label{tab1}
REE}
\centering
\begin{tabular}{rrrr}
U & a & b & c\\
\hline
1 & 1 & 0 & 2\\
2 & 2 & 0 & 3\\
3 & 1 & 1 & 1\\
4 & 1 & 1 & 1\\
5 & 2 & 1 & 3\\
6 & 1 & 0 & 3\\
\end{tabular}
\end{table}

\(a_1b_0c_2,a_2b_0c_3,a_1b_1c_1,a_2b_1c_3,a_1b_0c_3\) are all basic formulas in the KR-system.
The characteristic formula of the system is
\begin{equation*}
a_1b_0c_2\vee a_2b_0c_3\vee a_1b_1c_1\vee a_2b_1c_3\vee a_1b_0c_3
\end{equation*}

Specific axioms of DL-logic
\begin{enumerate}
\item \((a,v)\wedge(a,u)\equiv 0\) for any \(a\in A,u,v\in V\) and \(v\neq u\)
\item \(\displaystyle\bigvee_{v\in V_a}(a,v)\equiv 1\) for every \(a\in A\)
\item \(\sim(a,v)\equiv\displaystyle\bigvee_{\substack{u\in V_a\\ u\neq v}}(a,u)\) for every
\(a\in A\)
\end{enumerate}


\begin{proposition}[7.3]
\begin{equation*}
\models_S \displaystyle\sum_{S}(P)\equiv 1,\;\text{ for any } 
P\subseteq A
\end{equation*}
\end{proposition}

The axiom (1) follows from the assumption that each object can have exactly
one value of each attribute.

The second axiom (2) follows from the assumption that each attribute must
take one of the values of its domain for every object in the system. 

The axiom (3) allows us the get rid of negation in such a way that instead of
saying that an object does not posses a given property we can say that it has
one of the remaining properties.

The Proposition 7.3 means that the knowledge contained in the knowledge
representation system is the whole knowledge available at the present stage,
and corresponds to so called closed world assumption (CWA).


A formula \(\phi\) is \textbf{derivable} from a set of formulas \(\Omega\), denoted \(\Omega\vdash\phi\) if
and only if it's derivable from axioms and formulas of \(\Omega\) by finite
application of modus ponens

Formula \(\phi\) is a \textbf{theorem} of DL-logic, symbolically \(\vdash \phi\) if it's derivable
from the axioms only


A set of formulas \(\Omega\) is \textbf{consistent} if and only if the formula \(\phi\wedge\sim\phi\) is not
derivable from \(\Omega\)
\subsection{Normal forms}
\label{sec:orge5b34df}
Let \(P\subseteq A\) and \(\phi\) be a formula.

\(\phi\) is in a \(P\textbf{-normal form}\) in \(S\) if and only if either \(\phi\) is 0 or \(\phi\)
is 1, or \(\phi\) is a disjunction of nonempty \(P\text{-basic}\) formulas in \(S\)

\(A\text{-normal}\) form will be referred to as \textbf{normal form}

\begin{proposition}[7.4]
Let \(\phi\) be a formula in DL-language and let \(P\) contain all attributes
occurring in \(\phi\). Moreover assume axioms (1)-(3) and the formulas \(\sum_S(A)\).
Then there is a formula \(\psi\) in the \(P\text{-normal}\) form s.t. \(\vdash\phi\equiv\psi\)
\end{proposition}
\subsection{Decision rules and decision algorithms}
\label{sec:orgd4423d9}
Any implication \(\phi\to\psi\) will be called a \textbf{decision rule} in the KR-langauge. \(\phi\)
and \(\psi\) are referred to as the \textbf{predecessor} and the \textbf{successor} of \(\phi\to\psi\)
respectively. 

If a decision rule \(\phi\to\psi\) is true in \(S\), we will say that the decision rule
is \textbf{consistent} in \(S\), otherwise \textbf{inconsistent}

If \(\phi\to\psi\) is a decision rule and \(\phi\) and \(\psi\) are \(P\text{-basic}\) and
\(Q\text{-basic}\) formulas respectively, then the decision rule \(\phi\to\psi\) will
be called a \(PQ\textbf{-basic}\) \textbf{decision rule} (in short \(PQ\textbf{-rule}\))
or \textbf{basic rule} when \(PQ\) is
known.

If \(\phi_1 \to \psi,\phi_2 \to\psi,\dots,\phi_n \to\psi\) are basic decision rules
then the decision rule \(\phi_1 \vee\phi_2 \vee\dots\vee\phi_n \to\psi\) will be
called \textbf{combination} of basic decision rules \(\phi_1 \to \psi,\phi_2
   \to\psi,\dots,\phi_n \to\psi\) or in short  \textbf{combined} decision rule.

A \(PQ\text{-rule}\) \(\phi\to\psi\) is \textbf{admissible} in \(S\) if \(\phi\wedge\psi\) is satisfiable in \(S\)

\begin{proposition}[7.5]
A \(PQ\text{-rule}\) is true(consistent) if and only all \linebreak 
\(\lb P\cup Q\rb\text{-basic}\) formulas which occur in the 
\(\lb P\cup Q\rb\text{-normal}\)
form of the predecessor of the rule also occur in the 
\(\lb P\cup Q\rb\text{-normal}\) form of the successor of the rule. Otherwise the
rule is false 
\end{proposition}

For example, the rule \(b_0 \to c_2\) is false in \ref{tab1}, because the 
\(\lb b,c\rb\text{-normal}\) form of \(b_0\) is \(b_0 c_2 \vee b_0 c_3\), 
\(\lb b,c\rb\text{-normal}\) form of \(c_2\) is \(b_0 c_2\)

Any finite set of decision rules in a DL-language is referred to as a
\textbf{decision algorithm} in the DL-language

Algorithm here means a set of instructions(decision rules)

Any finite set of basic decision rules will be called a \textbf{basic decision algorithm}.

If all decision rules in a basic decision algorithm are 
\(PQ\text{-decision}\) rules, then the algorithm is said to be 
\(PQ\textbf{-decision}\) \textbf{algoritbm}, or in short\\
\(PQ\textbf{-algorithm}\) , and will be denoted by \((P,Q)\)

A \(PQ\text{-algorithm}\) is \textbf{admissible} in \(S\) if the algorithm is the set of
all \(RP\text{-rules}\) admissible in \(S\)

A \(PQ\text{-algorithm}\) is \textbf{complete} in \(S\) if for every \(x\in U\) there exists
a \(PQ\text{-decision}\) rule \(\phi\to\psi\) in the algorithm s.t. \(x\models\phi\wedge\psi\)
in \(S\). Otherwise the algorithm is \textbf{incomplete}

The \(PQ\text{-algorithm}\) is \textbf{consistent} in \(S\) if and only if all its
decision rules are consistent(true) in \(S\). Otherwise \textbf{inconsistent}


Thus when we are given a KR-system, then any two arbitrary, nonempty subsets
of attributes \(P,Q\) in the system, determine uniquely a 
\(PQ\text{-decision}\) algorithm and a decision table with \(P\) and \(Q\) as
condition and decision attributes respectively. Hence a 
\(PQ\text{-algorithm}\) and
\(PQ\text{-decision}\) table may be considered as 
equivalent concepts.

Consider
\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 1 & 1\\
2 & 2 & 1 & 0 & 1 & 0\\
3 & 2 & 1 & 2 & 0 & 2\\
4 & 1 & 2 & 2 & 1 & 1\\
5 & 1 & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}
and assume \(P=\lb a,b,c\rb\) and \(Q=\lb d,e\rb\) are condition and decision
attributes. Sets \(P\) and \(Q\) uniquely associate the following
\(PQ\text{-decision}\) algorithm with the table:
\begin{align*}
  &a_1b_0c_2\to d_1e_1\\
  &a_2b_1c_0\to d_1e_0\\
  &a_2b_1c_2\to d_0e_2\\
  &a_1b_2c_2\to d_1e_1\\
  &a_1b_2c_0\to d_0e_2\\
\end{align*}
\subsection{Truth and indiscernibility}
\label{sec:org3824891}
\begin{proposition}[7.6]
A \(PQ\text{-decision}\) rule \(\phi\to\psi\) in a \(PQ\text{-decision}\) algorithm is
consistent(true) in \(S\) if and only if for any \(PQ\text{-decision}\) rule
\(\phi'\to\psi'\) in \(PQ\text{-decision}\) algorithm, \(\phi=\phi'\) implies \(\psi=\psi'\)
\end{proposition}

\begin{remark}
in order to check whether or not a decision rule
\(\phi\to\psi\) is true we have to show that the predecessor of the rule (the formula
\(\phi\)  discerns the decision class \(\psi\) from the remaining decision classes of
the decision  algorithm in question. Thus the concept of truth is somehow
replaced by the concept of indiscernibility.
\end{remark}
\subsection{Dependency of attributes}
\label{sec:org635635d}
The set of attributes \(Q\) \textbf{depends totally} (or in short \textbf{depends}) on the set of
attributes \(P\) in \(S\) if there exists a consistent \(PQ\text{-algorithm}\) in
\(S\), denoted by \(P\Ra_SQ\)

\emph{It can be easily seen that the concept of dependency of attributes
corresponds exactly to that introduced in CHAPTER 4}

The set of attributes \(Q\) \textbf{depends partially} on the set of attributes \(P\) in
\(S\) if there exists an inconsistent \(PQ\text{-algorithm}\) in \(S\)

Let \((P,Q)\) be a \(PQ\text{-algorithm}\) in \(S\). By a \textbf{positive region} of the
algorithm \((P,Q)\) denoted \(POS(P,Q)\) we mean the set of all consistent
\(PQ\text{-rules}\) in the algorithm.

In other words, the positive region of the decision algorithm \((P,Q)\) is the
consistent part of the inconsistent algorithm

With every \(PQ\text{-decision}\) algorithm we can associate a number\\
\(k=card\; POS(P,Q)/card\;(P,Q)\), called the \textbf{degree of consistency} of the
algorithm, or in short the \textbf{degree} of the algorithm, we will say that the
\(PQ\text{-algorithm}\) has the degree \(k\)

If a \(PQ\text{algorithm}\) has degree \(k\) we can say that the set of
attributes \(Q\) \textbf{depends in degree} \(k\) on the set of attributes \(P\), and we
will write \(P\Ra_k Q\)
\subsection{Reduction of consistent algorithms}
\label{sec:orgfdae597}
Let \((P,Q)\) be a consistent algorithm, and \(a\in P\). Attribute \(a\) is
\textbf{dispensable} in the algorithm \((P,Q)\) if and only if the algorithm 
\(((P-\lb a\rb),Q)\) is consistent. Otherwise \textbf{indispensable}

If all attributes \(a\in P\) are dispensable in the algorithm \((P,Q)\) then the
algorithm \((P,Q)\) will be called \textbf{independent}

The subset of attributes \(R\subseteq P\) will be called a \textbf{reduct} of \(P\) in the
algorithm \((P,Q)\) if the algorithm \((R,Q)\) is independent and consistent.
\((R,Q)\) is a \textbf{reduct} of \((P,Q)\)

The set of all indispensable attributes in an algorithm \((P,Q)\) will be
called the \textbf{core} of the algorithm \((P,Q)\), denoted by \(CORE(P,Q)\)

\begin{proposition}[7.7]
\begin{equation*}
CORE(P,Q)=\bigcup RED(P,Q)
\end{equation*}
where \(RED(P,Q)\) is the set of reducts of \((P,Q)\)
\end{proposition}

Consider
\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 1 & 1\\
2 & 2 & 1 & 0 & 1 & 0\\
3 & 2 & 1 & 2 & 0 & 2\\
4 & 1 & 2 & 2 & 1 & 1\\
5 & 1 & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}
and the \(PQ\text{-algorithm}\) in the system shown below
\begin{align*}
  &a_1b_0c_2\to d_1e_1\\
  &a_2b_1c_0\to d_1e_0\\
  &a_2b_1c_2\to d_0e_2\\
  &a_1b_2c_2\to d_1e_1\\
  &a_1b_2c_0\to d_0e_2\\
\end{align*}
where \(P=\lb a,c,b\rb\) and \(Q=\lb d,e\rb\) are condition and decision
attributes.

There are two reducts of \(P\), namely \(\lb a,c\rb\) and \(\lb b,c\rb\)

Note that

\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 1 & 1\\
4 & 1 & 2 & 2 & 1 & 1\\
\hline
2 & 2 & 1 & 0 & 1 & 0\\
\hline
3 & 2 & 1 & 2 & 0 & 2\\
5 & 1 & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}

remove \(a\) we get
\begin{center}
\begin{tabular}{rrrrr}
U & b & c & d & e\\
\hline
1 & 0 & 2 & 1 & 1\\
4 & 2 & 2 & 1 & 1\\
\hline
2 & 1 & 0 & 1 & 0\\
\hline
3 & 1 & 2 & 0 & 2\\
5 & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}
remove b we get
\begin{center}
\begin{tabular}{rrrrr}
U & a & c & d & e\\
\hline
1 & 1 & 2 & 1 & 1\\
4 & 1 & 2 & 1 & 1\\
\hline
2 & 2 & 0 & 1 & 0\\
\hline
3 & 2 & 2 & 0 & 2\\
5 & 1 & 0 & 0 & 2\\
\end{tabular}
\end{center}
remove c we get
\begin{center}
\begin{tabular}{rrrrr}
U & a & b & d & e\\
\hline
1 & 1 & 0 & 1 & 1\\
4 & 1 & 2 & 1 & 1\\
\hline
2 & 2 & 1 & 1 & 0\\
\hline
3 & 2 & 1 & 0 & 2\\
5 & 1 & 2 & 0 & 2\\
\end{tabular}
\end{center}
\subsection{Reduction of inconsistent algorithms}
\label{sec:org6dbcc2c}
Let \((P,Q)\) be a inconsistent algorithm, and \(a\in P\)

An attribute \(a\) is \textbf{dispensable} in \(PQ\text{-algorithm}\) if
\(POS(P,Q)=POS((P-\lb a\rb),Q)\).
\subsection{reduction of decision rules}
\label{sec:org8949837}
If \(\phi\) is \(P\text{-basic}\) formula and \(Q\subseteq P\) then by \(\phi/Q\) we
mean the \(Q\text{-basic}\) formula obtained from the formula \(\phi\) by removing
from \(\phi\) all elementary formulas \((a,v_a)\) s.t. \(a\in P-Q\)

Let \(\phi\to\psi\) be a \(PQ\text{-rule}\) and let \(a\in P\). Attribute \(a\) is
\textbf{dispensable} in the rule \(\phi\to\psi\) if and only if
\begin{equation*}
\models_S\phi\to\psi \text{ implies } \models \phi/(P-\lb a \rb)\to \psi
\end{equation*}

If all attributes \(a\in P\) are dispensable in \(\phi\to\psi\) then \(\phi\to\psi\)
will be called \textbf{independent}

The subset of attributes \(R\subseteq P\) will be called a \textbf{reduct} of
\(PQ\text{-rule}\) \(\phi\to\psi\) if \(\phi/R\to\psi\) is independent and
\(\models_S\phi\to\psi\) implies \(\models_S\phi/R\to\psi\)

If \(R\) is a reduct of the \(PQ\text{-rule}\) \(\phi\to\psi\), then \(\phi/R\to\psi\)
is said to be \textbf{reduced}

The set of all indispensable attributes in \(\phi\to\psi\) will be called the
core of \(\phi\to\psi\), and will be denoted by \(CORE(\phi\to\psi)\).

\begin{proposition}[7.8]
\begin{equation*}
CORE(P\to Q)=\bigcap RED(P\to Q)
\end{equation*}
\end{proposition}

There are two possibilities available at the moment. First we may reduce the
algorithm, i.e. drop all dispensable condition attributes in the whole algorithm 
and afterwards reduce each decision rule in the reduced algorithm, i.e. drop all
unnecessary conditions in each rule of the algorithm. The second option consists
in reduction, at the very beginning, of decision rules, without the
elimination of attributes from the whole algorithm

First
\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 2 & 1 & 1\\
2 & 2 & 1 & 0 & 1 & 0\\
3 & 2 & 1 & 2 & 0 & 2\\
4 & 1 & 2 & 2 & 1 & 1\\
5 & 1 & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}
where \(P=\lb a,b,c\rb\) and \(Q=\lb d,e\rb\)
\begin{align*}
   &a_1b_0c_2\to d_1e_1\\
   &a_2b_1c_0\to d_1e_0\\
   &a_2b_1c_2\to d_0e_2\\
   &a_1b_2c_2\to d_1e_1\\
   &a_1b_2c_0\to d_0e_2\\
 \end{align*}
For the first rule \(a_1b_0c_2\to d_1e_1\), the core of it is the empty set.
Either of the conditions \(b_0c_2,a_1c_2,a_1b_0\) uniquely determine the
decision \(d_1e_1\). There are two reduct, namely \(\lb b\rb\) and \(\lb a,c\rb\)

Below is the cores of each decision rule
\begin{center}
\begin{tabular}{rllrrr}
U & a & b & c & d & e\\
\hline
1 & - & - & - & 1 & 1\\
2 & - & - & 0 & 1 & 0\\
3 & - & - & 2 & 0 & 2\\
4 & - & - & 2 & 1 & 1\\
5 & - & - & 0 & 0 & 2\\
\end{tabular}
\end{center}
And
\begin{center}
\begin{tabular}{lllrrr}
U & a & b & c & d & e\\
\hline
1 & - & 0 & - & 1 & 1\\
1' & 1 & - & 2 & 1 & 1\\
\hline
2 & 2 & - & 0 & 1 & 0\\
2' & - & 1 & 0 & 1 & 0\\
\hline
3 & 2 & - & 2 & 0 & 2\\
3' & - & 1 & 2 & 0 & 2\\
\hline
4 & 1 & - & 2 & 1 & 1\\
4' & - & 2 & 2 & 1 & 1\\
\hline
5 & 1 & - & 0 & 0 & 2\\
5' & - & 2 & 0 & 0 & 2\\
\end{tabular}
\end{center}
Note that 1' and 4 are identical.

\subsection{Minimization of decision algorithm}
\label{sec:orgafbffb6}
Let \(\A\) be a basic algorithm and let \(S=(U,A)\) be a KR-system. The set of all
basic rules in \(\A\) having the same successor \(\psi\) will be denoted
\(\A_\psi\), and \(\P_\psi\) is the set of all predecessors of decision rules
belonging to \(\A_\psi\)

A basic decision rule \(\phi\to\psi\) in \(\A\) is \textbf{dispensable} in \(\A\) if
\(\models_S\bigvee\bP_\psi\equiv\bigvee\lb\P_\psi-\lb\phi\rb\rb\). Otherwise
\textbf{indispensable}

A subset \(\A'\) of decision rules of \(\A_\psi\) is a \textbf{reduct} of \(\A_\psi\) if all
decision rules in \(\A'\) are independent and
\(\models_S\bigvee\P_\psi\equiv\bigvee\P'_\psi\) 

A set of decision rules \(\A_\psi\) is \textbf{reduced} if reduct of \(\A_\psi\) is
\(\A_\psi\) itself

A basic algorithm \(\A\) is \textbf{minimal} if every decision rule in \(\A\) is reduced
and for every decision rule \(\phi\to\psi\) in \(\A\), \(\A_\psi\) is reduced

Thus in order to simplify a PQ-algorithm, we must first reduce the set of
attributes, i.e. we present the algorithm in a normal form (note that many
normal forms are possible in general). The next step consists in the reduction
of the algorithm, i.e. simplifying the decision rules. The last step removes
all superfluous decision rules from the algorithm.
$abc$

Given
\begin{center}
\begin{tabular}{rrrrrr}
U & a & b & c & d & e\\
\hline
1 & 1 & 0 & 0 & 1 & 1\\
2 & 1 & 0 & 0 & 0 & 1\\
3 & 0 & 0 & 0 & 0 & 0\\
4 & 1 & 1 & 0 & 1 & 0\\
5 & 1 & 1 & 0 & 2 & 2\\
6 & 2 & 2 & 0 & 2 & 2\\
7 & 2 & 2 & 2 & 2 & 2\\
\end{tabular}
\end{center}
and assume \(P=\lb a,b,c,d\rb\) and \(Q=\lb e\rb\) are condition and decision attributes

The only \(e\text{-dispensable}\) condition attribute is \(c\)
\begin{center}
\begin{tabular}{rrrrr}
U & a & b & d & e\\
\hline
1 & 1 & 0 & 1 & 1\\
2 & 1 & 0 & 0 & 1\\
3 & 0 & 0 & 0 & 0\\
4 & 1 & 1 & 1 & 0\\
5 & 1 & 1 & 2 & 2\\
6 & 2 & 2 & 2 & 2\\
7 & 2 & 2 & 2 & 2\\
\end{tabular}
\end{center}
In the next step we have to reduce the superfluous values of attributes, i.e.
reduce all decision rules in the algorithm. To this end we have first computed
core values of attributes
\begin{center}
\begin{tabular}{rlllr}
U & a & b & d & e\\
\hline
1 & - & 0 & - & 1\\
2 & 1 & - & - & 1\\
3 & 0 & - & - & 0\\
4 & - & 1 & 1 & 0\\
5 & - & - & 2 & 2\\
6 & - & - & - & 2\\
7 & - & - & - & 2\\
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{rlllr}
U & a & b & d & e\\
\hline
1 & 1 & 0 & \texttimes{} & 1\\
1' & \texttimes{} & 0 & 1 & 1\\
2 & 1 & 0 & \texttimes{} & 1\\
2' & 1 & \texttimes{} & 0 & 1\\
\hline
3 & 0 & \texttimes{} & \texttimes{} & 0\\
4 & \texttimes{} & 1 & 1 & 0\\
\hline
5 & \texttimes{} & \texttimes{} & 2 & 2\\
6 & 2 & \texttimes{} & \texttimes{} & 2\\
6' & \texttimes{} & 2 & \texttimes{} & 2\\
6'' & \texttimes{} & \texttimes{} & 2 & 2\\
7 & 2 & \texttimes{} & \texttimes{} & 2\\
7' & \texttimes{} & 2 & \texttimes{} & 2\\
7'' & \texttimes{} & \texttimes{} & 2 & 2\\
\end{tabular}
\end{center}
Hence
\begin{align*}
  &a_1b_0\to e_1\\
  &a_0\vee b_1d_1\to e_0\\
  &d_2\to e_2\\
\end{align*}
\end{document}